The problem of routing an input job stream to one of several parallel processing stations, each with a finite buffer, so as to minimize the probability of blocking has conventionally been treated using state-independent or state-dependent approaches. Blocking in the sense used here means that an arriving job from the stream cannot be routed to any station because the buffers in all stations are full.
Representative of the state-independent approach is the description contained in the article entitled "The Optimal Input Rates to a System of Manufacturing Cells", by D. D. Yao and J. G. Shanthikumar, and published in INFOR Vol. 25, No. 1, pg. 57-65, 1987. Yao et al have supplied a routing technique by deriving an optimum Bernoulli split of the arrival stream, making use of convexity properties of a so-called loss-rate function defined by Yao et al. However, such a routing method does not take into account the various states of the stations, and therefore the optimization is restricted to the framework of state-independent decision rules and routing methods.
An optimum state-dependent assignment or routing rule may be derived with the assumption of Poisson arrivals for the jobs and exponential service-time distributions for the stations and by solving the associated finite-state Markov decision process. The technique is state-dependent since information about the state of each processing station, such as the total number of jobs assigned to each buffer, is available and may be used for computation by a front-end routing processor. However, the state-space grows very rapidly with buffer capacities and this limits the size of systems that may be solved, particularly in real-time.